\documentclass[11pt]{article}

\usepackage{array}

\title{Exercise 1.13}

\author{Lindsey Kuper}

\date{\today}

\newcommand{\statement}[1]{\textbf{#1} \medskip}

\newcommand{\qed}{\hfill \rule{1.3ex}{1.3ex}}

\begin{document}

\maketitle

\statement{Prove that $Fib(n)$ is the closest integer to $\phi^n / \sqrt{5}$, where $\phi = (1 + \sqrt{5}) / 2$.}

We begin by making the conjecture $S(n): Fib(n) = ( \phi^n - \psi^n ) / \sqrt{5}$, where $\psi = (1 - \sqrt{5} / 2)$, and proving that $S(n)$ is true for all positive integers $n$.  The proof proceeds by induction on $n$.

\textit{Base case} ($n = 0$):  
\begin{eqnarray*}
  \frac{\left(\psi^0 - \phi^0\right)}{\sqrt{5}} & = & \frac{\left(1 - 1\right)}{\sqrt{5}} \\
& = & \frac{0}{\sqrt{5}} \\
& = & 0
\end{eqnarray*}
and $Fib(0) = 0$, therefore $S(0)$ is true.

\textit{Base case} ($n = 1$):
\begin{eqnarray*}
  \frac{\left(\psi^1 - \phi^1\right)}{\sqrt{5}} & = & \frac{  
  \frac{\left(1 + \sqrt{5}\right)}{2} -
  \frac{\left(1 - \sqrt{5}\right)}{2}
  }{\sqrt{5}} \\
& = & \frac{
\frac{2\sqrt{5}}{2}
}{\sqrt{5}} \\
& = & 1
\end{eqnarray*}
and $Fib(1) = 1$, therefore $S(1)$ is true.

\textit{Induction step}:  Assume the truth of the statements $S(0)$, $S(1)$, $\cdots$, $S(k-2)$, $S(k-1)$, and $S(k)$ for some positive integer $k \geq 1$.  Then
\begin{eqnarray*}
S(k + 1): Fib(k + 1) & = & \frac{\left(\phi^{k+1} - \psi^{k+1}\right)}{\sqrt{5}} \\
\end{eqnarray*}
which is equivalent to
\begin{eqnarray*}
Fib(k) + Fib(k-1) & = & \frac{\left(\phi^{k} - \psi^{k}\right)}{\sqrt{5}} +  \frac{\left(\phi^{k-1} - \psi^{k-1}\right)}{\sqrt{5}}
\end{eqnarray*}
by the definition of Fibonacci numbers.  
% And the transitive property of equality, maybe?  Do I even need to mention this?
We know that this is true from the truth of $S(k)$ and $S(k -1)$.  Therefore $S(n)$ is true for all positive integers $n$ by induction.\qed

\end{document}
